package tiruvury.InterviewPrep.DataStructures;

import java.util.Hashtable;

import tiruvury.InterviewPrep.HelperClasses.Node;

public class MyLinkedList
{
	Node root = null;

	public void CreateSpecificList(int[] data)
	{
		Node prevNode = null;
		Node currNode = null;
		for (int i = 0; i < data.length; i++)
		{
			currNode = new Node(data[i], null);

			if (root == null)
			{
				root = currNode;
			}

			if (prevNode != null)
			{
				prevNode.next = currNode;
			}
			prevNode = currNode;
		}
	}

	public void CreateRandomList(int numNodes)
	{
		System.out.println("Creating List");
		Node prevNode = null;
		Node currNode = null;
		for (int i = 0; i < numNodes; i++)
		{
			/*
			 * CODINGERROR: You initially wrote (int) Math.random() * 100, which
			 * always returns 0
			 */
			currNode = new Node((int) (Math.random() * 100), null);

			if (root == null)
			{
				root = currNode;
			}

			if (prevNode != null)
			{
				prevNode.next = currNode;
			}
			prevNode = currNode;
		}
	}

	public Node GetKthToLastNOde(int k)
	{
		if (k > 0 && root != null)
		{
			Node aptr = root;
			Node bptr = root;

			int i = 0;
			while (i < k && bptr != null)
			{
				bptr = bptr.next;
				i++;
			}

			if (i == k)
			{
				while (aptr != null && bptr != null)
				{
					aptr = aptr.next;
					bptr = bptr.next;
				}
				return aptr;
			}
		}
		return null;
	}

	public void PrintList()
	{
		System.out.println("Printing List");
		Node currNode = root;
		while (currNode != null)
		{
			if (currNode != root)
			{
				System.out.print(" -> ");
			}

			System.out.print(currNode.data);
			currNode = currNode.next;
		}

	}

	public Node GetRoot()
	{
		return root;
	}

	/*
	 * CODINGERROR
	 * When you are writing a recursive function, make sure you *don't* change
	 * the parameters passed in. In this case, don't change what currNode and
	 * prevNode mean through the course of the function. That way,
	 * whenever/wherever you access them in the function, they will stay the
	 * same.
	 * 
	 * If you change what they mean, say like this:
	 * prevNode = currNode;
	 * currNode = currNode.next;
	 * ReverseList(currNode, prevNode);
	 * and you access prevNode/currNode later, they are not what you thought
	 * they would be as they are now one node ahead of where they pointed to
	 * earlier.
	 */
	public void ReverseList(Node currNode, Node prevNode)
	{
		if (currNode.next != null)
		{
			ReverseList(currNode.next, currNode);
		}
		else
		{
			// We have reached the end of the linked list. This is the new root.
			root = currNode;
		}

		currNode.next = prevNode;
		return;
	}

	public void IterativeReverseList()
	{
		System.out.println();
		System.out.println("Reverse List (Iterative)");
		Node currNode = root;
		Node prevNode = null;
		Node nextNode = null;

		while (currNode != null)
		{
			nextNode = currNode.next;
			currNode.next = prevNode;
			prevNode = currNode;
			currNode = nextNode;
		}
		root = prevNode;
	}

	public void RemoveDuplicates()
	{
		System.out.println("Removing Duplicates");
		Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();

		Node currNode = root;
		Node prevNode = null;
		Node removedNode = null;

		while (currNode != null)
		{
			// Check if currNode.data is in the hashTable
			/*
			 * CODINGERROR
			 * You used contains() instead of containsKey and that led to
			 * unexpected results
			 */
			if (ht.containsKey(currNode.data))
			{
				prevNode.next = currNode.next;
				removedNode = currNode;
			}
			else
			{
				ht.put(currNode.data, 1);
				prevNode = currNode;
			}
			currNode = currNode.next;
			if (removedNode != null)
			{
				removedNode.next = null;
				removedNode = null;
			}
		}
	}

	public void RemoveDuplicatesWithoutBuffer()
	{
		System.out.println("Removing Duplicates Without Buffer");

		Node curr = root;
		Node runner = null;
		Node prev = null;
		Node removedNode = null;
		while (curr != null)
		{
			prev = curr;
			runner = curr.next;
			while (runner != null)
			{
				/*
				 * CODINGERROR
				 * Advance the prevPtr only if a duplicate was not found.
				 * Earlier, you were always advancing
				 * the prevPtr. So if a duplicate was found, the duplicate is
				 * removed, but prevPtr will now
				 * point to the removed note if you wrongly advance here. If has
				 * to be in the else block and
				 * not outside.
				 */
				if (curr.data == runner.data)
				{
					prev.next = runner.next;
					removedNode = runner;
				}
				else
				{
					prev = runner;
				}
				runner = runner.next;
				if (removedNode != null)
				{
					removedNode.next = null;
					removedNode = null;
				}
			}
			curr = curr.next;
		}
	}

	public void RemoveNodeFromListGivenOnlyThatNode(Node nodeToRemove)
	{
		Node removedNode = null;
		if (nodeToRemove == null)
		{
			// Nothing to remove
			return;
		}

		if (nodeToRemove.next == null)
		{
			// Cannot delete if node is last node in list
			return;
		}

		nodeToRemove.data = nodeToRemove.next.data;
		removedNode = nodeToRemove.next;
		nodeToRemove.next = nodeToRemove.next.next;
		if (removedNode != null)
		{
			removedNode.next = null;
			removedNode = null;
		}
	}

	public void InsertNodeToSortedList(Node node)
	{
		if (node == null)
		{
			return;
		}

		if (root == null)
		{
			root = node;
			return;
		}

		Node prev = null;
		Node curr = root;

		while (curr != null)
		{
			if (prev != null)
			{
				if (node.data >= prev.data && node.data <= curr.data)
				{
					node.next = curr;
					prev.next = node;
					/*
					 * SYNTAXERROR: You just had a break here earlier. While
					 * thats right, the last two lines which shouldn't get
					 * executed always will.
					 * So you should return instead of breaking.
					 */
					return;
				}
			}
			else
			{
				if (node.data <= curr.data)
				{
					node.next = curr;
					root = node;
					return;
				}
			}

			prev = curr;
			curr = curr.next;
		}

		// You'll reach here if the node never got inserted, which means its the
		// largest value node.
		// Should be inserted at the end.
		prev.next = node;
		node.next = null;
	}

	public void PartitionAndJoinAroundX(int x)
	{
		System.out.println("Partitioning list around " + x);
		Node smallPtr = null;
		Node largePtr = null;

		Node smallList = null;
		Node largeList = null;

		Node currPtr = root;
		Node prevPtr = null;

		while (currPtr != null)
		{
			if (currPtr.data < x)
			{
				if (smallPtr == null)
				{
					smallPtr = currPtr;

					/*
					 * CODINGERROR
					 * You forgot to cache the start of the smallList, which is
					 * the new root of the
					 * partitioned list.
					 */
					smallList = smallPtr;
				}
				else
				{
					smallPtr.next = currPtr;
					smallPtr = currPtr;
				}
			}
			else
			{
				if (largePtr == null)
				{
					largePtr = currPtr;
					/*
					 * CODINGERROR
					 * You forgot to cache the root of the large list, which is
					 * what needs to be
					 * "appended" to the small list.
					 */
					largeList = largePtr;
				}
				else
				{
					if (currPtr.data > x)
					{
						largePtr.next = currPtr;
						largePtr = currPtr;
					}
					else
					{
						/*
						 * CODINGERROR
						 * You want to insert the current node at the beginning
						 * of the list.
						 * If you just re-purpose the current node,
						 * currentNode.next is no longer the
						 * "previous" next node, but the first node of the list
						 * before which this is being
						 * inserted. You're doing current = current->next, so
						 * watch out.
						 */
						Node newNode = new Node(currPtr.data, largeList);
						largeList = newNode;

						/*
						 * CODINGERROR
						 * Since you are copying the node, you must effectively
						 * "delete" the node
						 * in its current location. Which means its previous
						 * node should now point to
						 * the node following the current node.
						 */
						prevPtr.next = currPtr.next;
					}
				}
			}

			prevPtr = currPtr;
			currPtr = currPtr.next;
		}

		/*
		 * CODINGERROR
		 * Your last node could be a node in the middle of the list. Fix its
		 * next link to null, or you'll get infinite loops
		 */
		largePtr.next = null;

		/*
		 * CODINGERROR
		 * You were appending smallPtr to largePtr. That means you're appending
		 * the end of the
		 * small list to the end of the large list, instead of beginning.
		 */
		smallPtr.next = largeList;
		root = smallList;
	}

	public void PartitionAndJoinAroundX1(int x)
	{
		Node smallList = null;
		Node largeList = null;
		Node smallPtr = null;
		Node largePtr = null;
		Node currPtr = root;
		Node prevPtr = null;

		while (currPtr != null)
		{
			if (currPtr.data < x)
			{
				if (smallList == null)
				{
					smallList = smallPtr = currPtr;
				}
				else
				{
					smallPtr.next = currPtr;
					smallPtr = smallPtr.next;
				}
			}
			else if (currPtr.data >= x)
			{
				if (largeList == null)
				{
					largeList = largePtr = currPtr;
				}
				else
				{
					if (currPtr.data > x)
					{
						largePtr.next = currPtr;
						largePtr = largePtr.next;
					}
					else
					{
						prevPtr.next = currPtr.next;
						currPtr.next = largeList;
						largeList = currPtr;
						currPtr = prevPtr;
					}
				}
			}
			prevPtr = currPtr;
			currPtr = currPtr.next;
		}

		if (smallList != null && smallPtr != null)
		{
			root = smallList;
			if (largeList != null && largePtr != null)
			{
				smallPtr.next = largeList;
				largePtr.next = null;
			}
		}
		else
		{
			if (largeList != null && largePtr != null)
			{
				root = largeList;
			}
		}
	}

	public boolean IsListPalindrome()
	{
		if (root == null)
			return false;

		int listLength = getListLength(root);
		if (listLength == 1)
			return true;

		Node returnedNode = checkPalindrome(root, root, 0, listLength - 1);

		return (returnedNode != null);
	}

	private Node checkPalindrome(Node currNode, Node root, int startIdx, int endIdx)
	{
		if (currNode == null || root == null)
			return root;

		/*
		 * CODINGERROR: WHENVER U ARE INCREMENTING/DECREMENTING VALUES IN
		 * FUNCTION CALLS, DONT CHANGE THE ORIGINAL VALUE.
		 * WHICH MEANS, DO NOT PASS IN PARAMS LIKE ++startIdx or startIdx++.
		 * Pass in startIdx + 1.
		 * Side Note: If you pass in startIdx++ to a function call, the
		 * increment happens after the function call.
		 * Variable BeforeCall FunctionCallArg AfterCall ValuePassedToCallee
		 * i 1 ++i 2 2
		 * i 1 i++ 2 1
		 * i 1 i+1 1 2
		 */
		Node oppNode = checkPalindrome(currNode.next, root, startIdx + 1, endIdx - 1);

		if (oppNode == null || (oppNode != null && endIdx > startIdx))
		{
			return oppNode;
		}

		if (currNode.data == oppNode.data)
		{
			return oppNode.next;
		}

		return null;
	}

	// 5. Find length of a linked list loop
	int getLinkedListLoopLength(Node root)
	{
		int len = 0;
		boolean hasLoop = false;

		Node slowPtr = root;
		Node fastPtr = root;

		// Step 1: Detect whether there's a loop or not.
		// At the end of the step, you're at the meeting point of the slow and
		// fast pointers
		while (slowPtr != null && fastPtr != null)
		{
			slowPtr = slowPtr.next;
			fastPtr = (fastPtr.next != null) ? fastPtr.next.next : fastPtr.next;

			if (slowPtr == fastPtr)
			{
				hasLoop = true;
				break;
			}
		}

		if (hasLoop)
		{
			// Step 2. Detect the start of the loop
			// KEY POINT: The start of the loop is always equidistant from a)
			// the start of the linked list and b) the meeting point of the fast
			// and slow pointers. (Remember Nandhini's diagram). Which means, if
			// you advance the slow pointer from where it is now and another
			// pointer from the root, they will meet at the start of the linked
			// list loop.
			Node curr = root;

			while (curr != slowPtr)
			{
				curr = curr.next;
				slowPtr = slowPtr.next;
			}

			// Step 3. Set the current pointer to loop start and increment
			// length till you reach the same spot again, to get the length of
			// the loop.
			Node loopStart = curr;
			while (true)
			{
				len++;
				curr = curr.next;
				if (curr == loopStart)
				{
					break;
				}
			}
			len++;
		}

		return len;
	}

	public Node FindMiddle()
	{
		if (root == null)
			return null;

		Node slowPtr = root;
		Node fastPtr = root;

		while (fastPtr.next != null && fastPtr.next.next != null)
		{
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}

		return slowPtr;
	}

	private int getListLength(Node node)
	{
		if (node == null)
			return 0;

		int len = 1;

		while (node.next != null)
		{
			len++;
			node = node.next;
		}

		return len;
	}
}
